import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{0,2,1};
        for(int e: s.countSmaller(nums)) {
            System.out.print(e + " ");
        }
    }

    public List<Integer> countSmaller1(int[] nums) {
        /**
         * 计算右侧小于当前元素的个数
         * 解法1：暴力枚举-超时（很容易想到会超时，因为这是一道困难题，要是暴力能做才是怪事）*/
        // 1 预处理
        int n = nums.length;

        // 2 计算
        List<Integer> retList = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            int tempCount = 0;
            for(int j = i+1; j < n; j++) {
                if(nums[i] > nums[j]) {
                    tempCount ++;
                }
            }
            retList.add(tempCount);
        }

        // 3 返回值
        return retList;
    }

    public List<Integer> countSmaller(int[] nums) {
        /**
         * 计算右侧小于当前元素的个数
         * 解法2：基于暴力解法使用分治 + 排序的思想计算
         * 遇见问题：
         *      由于我对左右部分都排了降序，因此当我在合并有序数组中按照下标写入count数组时，这个元素的位置已经发生改变，就导致位置错误
         * 解决方法：
         *      在将nums修改为二维数组传递，nums[x][1]保存原索引
         * 本题核心思想：
         *      追踪数组原索引，为了保证索引正确，单独开辟空间维护*/
        // 1 预处理
        int n = nums.length;
        int[] count = new int[n];
        // -将nums修改为int[n][2]结构，其中arr[x][0]表示值，arr[x][1]表示原索引
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }
        List<Integer> retList = new LinkedList<>();
        // 2 归并排序
        mergeSort(0, n-1, arr, count);
        // 3 返回值
        for(int e: count) {
            retList.add(e);
        }
        return retList;
    }

    public static int[][] tempArray = new int[10_0000][2];

    public static void mergeSort(int left, int right, int[][] nums, int[] count) {
        /**
         * 使用归并排序优化暴力解法
         * 策略：找到一个元素后面有多少个比其小的元素（降序）
         * 参数：
         *  count：写入数组，传递一个同等大小数组以供在递归中写入
         * 优化：
         *  由于归并排序在处理时会修改元素位置，而本题需要求原数组每个元素右侧小于当前元素的个数，是严格要求位置的
         *  因此将nums和tempArray都设置为二维数组，在每次交换元素时，同步维护数组下标*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 递归左右分别计数
        int mid = left + (right - left) / 2;
        mergeSort(left, mid, nums, count);
        mergeSort(mid+1, right, nums, count);

        // 3 合并a、b计数
        int baseIndex = left;
        int n = right - left + 1;
        int i = 0;
        // -临时写入
        int left2 = mid + 1;
        while(left <= mid && left2 <= right) {
            if(nums[left][0] <= nums[left2][0]) {
                tempArray[i][0] = nums[left2][0];
                tempArray[i++][1] = nums[left2++][1];
            } else {
                // -利用单调性快速计算
                // -因为归并排序在处理过程中会修改元素位置，故将nums修改为二维数组，其中nums[x][1]存储原下标
                count[nums[left][1]] += (right - left2 + 1);
                tempArray[i][0] = nums[left][0];
                tempArray[i++][1] = nums[left++][1];
            }
        }
        while(left <= mid) {
            tempArray[i][0] = nums[left][0];
            tempArray[i++][1] = nums[left++][1];
        }
        while(left2 <= right) {
            tempArray[i][0] = nums[left2][0];
            tempArray[i++][1] = nums[left2++][1];
        }
        // -真实写入
        for(int j = 0; j < n; j++) {
            nums[baseIndex + j][0] = tempArray[j][0];
            nums[baseIndex + j][1] = tempArray[j][1];
        }
    }
}
